LeetCode 63、不同路径II

一、题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

现在考虑网格中有障碍物。问总共有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 不同路径II（ LeetCode 63 ）：https://leetcode-cn.com/problems/unique-paths-ii/
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // 设置二维数组 dp 用来储存到达每个位置时不同路径的数量
        // dp[0][0] 表示从第 0 行第 0 列到达第 0 行第 0 列时不同路径的数量
        // dp[0][i] 表示从第 0 行第 0 列到达第 0 行第 i 列时不同路径的数量
        // dp[j][0] 表示从第 0 行第 0 列到达第 j 行第 0 列时不同路径的数量
        // dp[i][j] 表示从第 0 行第 0 列到达第 i 行第 j 列时不同路径的数量

        // m 行
        int m = obstacleGrid.length;

        // n 列
        int n = obstacleGrid[0].length;

        int[][] dp = new int[m][n];

        // i 从 1 遍历到 m - 1 
        // 获取从第 0 行第 0 列到达第 j 行第 0 列时不同路径的数量
        // 由于每次只能向下或者向右移动一步，此时只能向下移动一步
        // 所以，只能一直向下走，只有这一条路径
        for(int i = 0; i < m ; i++){
            // 一旦出现了障碍，那么后面所有的位置都是到达不了的，都是默认的 0
            if(obstacleGrid[i][0] == 1)  break;

            // 仅此一条，别无分路
            dp[i][0] = 1;

        }

        // j 从 1 遍历到 n - 1 
        // 获取从第 0 行第 0 列到达第 0 行第 i 列时不同路径的数量
        // 由于每次只能向下或者向右移动一步，此时只能向右移动一步
        // 所以，只能一直向右走，只有这一条路径
        for(int j = 0; j < n ; j++){   
            // 一旦出现了障碍，那么后面所有的位置都是到达不了的，都是默认的 0
            if(obstacleGrid[0][j] == 1) break;
                 
            // 仅此一条，别无分路
            dp[0][j] = 1;
            
        }

        // 接下来从第 1 行到第 m - 1 行
        // 从第 1 列到 n - 1 列
        // 填充二维数组 dp 里面的值
        // dp[i][j] 表示从第 0 行第 0 列到达第 i 行第 j 列时不同路径的数量
        for (int i = 1; i < m; i++) {

            for (int j = 1; j < n; j++) {
                // 由于每次只能向下或者向右移动一步
                
                // 如果此时出现了障碍，那么由于无法到达这个位置，因此不用处理
                if (obstacleGrid[i][j] == 1) continue;

                // 位置 (i,j) 的不同路径的数量是由
                // 1、上边位置 dp[ i - 1 ][j] 的不同路径的数量
                // 2、左边位置 dp[i][ j - 1 ] 的不同路径的数量
                // 两者之和获取到的
                dp[i][j] = dp[ i - 1 ][j] + dp[i][ j - 1 ];
            }
        }

        // dp[ m - 1][ n - 1 ] 表示从第 0 行第 0 列到达第 m - 1 行第 n - 1 列时不同路径的数量
        // 即到达终点的数量
        // 返回这个结果即可
        return dp[ m - 1 ][ n - 1 ];
    }
}

**2、**C++ 代码

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
         // 设置二维数组 dp 用来储存到达每个位置时不同路径的数量
        // dp[0][0] 表示从第 0 行第 0 列到达第 0 行第 0 列时不同路径的数量
        // dp[0][i] 表示从第 0 行第 0 列到达第 0 行第 i 列时不同路径的数量
        // dp[j][0] 表示从第 0 行第 0 列到达第 j 行第 0 列时不同路径的数量
        // dp[i][j] 表示从第 0 行第 0 列到达第 i 行第 j 列时不同路径的数量

        // m 行
        int m = obstacleGrid.size();

        // n 列
        int n = obstacleGrid[0].size();

        auto dp = vector < vector < int>> ( m ,vector<int> ( n));

        // i 从 1 遍历到 m - 1 
        // 获取从第 0 行第 0 列到达第 j 行第 0 列时不同路径的数量
        // 由于每次只能向下或者向右移动一步，此时只能向下移动一步
        // 所以，只能一直向下走，只有这一条路径
        for(int i = 0; i < m ; i++){
            // 一旦出现了障碍，那么后面所有的位置都是到达不了的，都是默认的 0
            if(obstacleGrid[i][0] == 1)  break;

            // 仅此一条，别无分路
            dp[i][0] = 1;

        }

        // j 从 1 遍历到 n - 1 
        // 获取从第 0 行第 0 列到达第 0 行第 i 列时不同路径的数量
        // 由于每次只能向下或者向右移动一步，此时只能向右移动一步
        // 所以，只能一直向右走，只有这一条路径
        for(int j = 0; j < n ; j++){   
            // 一旦出现了障碍，那么后面所有的位置都是到达不了的，都是默认的 0
            if(obstacleGrid[0][j] == 1) break;
                 
            // 仅此一条，别无分路
            dp[0][j] = 1;
            
        }

        // 接下来从第 1 行到第 m - 1 行
        // 从第 1 列到 n - 1 列
        // 填充二维数组 dp 里面的值
        // dp[i][j] 表示从第 0 行第 0 列到达第 i 行第 j 列时不同路径的数量
        for (int i = 1; i < m; i++) {

            for (int j = 1; j < n; j++) {
                // 由于每次只能向下或者向右移动一步
                
                // 如果此时出现了障碍，那么由于无法到达这个位置，因此不用处理
                if (obstacleGrid[i][j] == 1) continue;

                // 位置 (i,j) 的不同路径的数量是由
                // 1、上边位置 dp[ i - 1 ][j] 的不同路径的数量
                // 2、左边位置 dp[i][ j - 1 ] 的不同路径的数量
                // 两者之和获取到的
                dp[i][j] = dp[ i - 1 ][j] + dp[i][ j - 1 ];
            }
        }

        // dp[ m - 1][ n - 1 ] 表示从第 0 行第 0 列到达第 m - 1 行第 n - 1 列时不同路径的数量
        // 即到达终点的数量
        // 返回这个结果即可
        return dp[ m - 1 ][ n - 1 ];

    }
};

3、Python 代码

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        # 设置二维数组 dp 用来储存到达每个位置时不同路径的数量
        # dp[0][0] 表示从第 0 行第 0 列到达第 0 行第 0 列时不同路径的数量
        # dp[0][i] 表示从第 0 行第 0 列到达第 0 行第 i 列时不同路径的数量
        # dp[j][0] 表示从第 0 行第 0 列到达第 j 行第 0 列时不同路径的数量
        # dp[i][j] 表示从第 0 行第 0 列到达第 i 行第 j 列时不同路径的数量

        # m 行
        m = len(obstacleGrid)

        # n 列
        n = len(obstacleGrid[0])

        dp = [[0] * n for _ in range(m)]


        # i 从 0 遍历到 m - 1 
        # 获取从第 0 行第 0 列到达第 j 行第 0 列时不同路径的数量
        # 由于每次只能向下或者向右移动一步，此时只能向下移动一步
        # 所以，只能一直向下走，只有这一条路径
        for i in range( 0 , m ):
            # 一旦出现了障碍，那么后面所有的位置都是到达不了的，都是默认的 0
            if obstacleGrid[i][0] == 1 :   break

            # 仅此一条，别无分路
            dp[i][0] = 1


        # j 从 0 遍历到 n - 1 
        # 获取从第 0 行第 0 列到达第 0 行第 i 列时不同路径的数量
        # 由于每次只能向下或者向右移动一步，此时只能向右移动一步
        # 所以，只能一直向右走，只有这一条路径
        for j in range( 0 , n ):
            # 一旦出现了障碍，那么后面所有的位置都是到达不了的，都是默认的 0
            if obstacleGrid[0][j] == 1 : break
                 
            # 仅此一条，别无分路
            dp[0][j] = 1
            
    

        # 接下来从第 1 行到第 m - 1 行
        # 从第 1 列到 n - 1 列
        # 填充二维数组 dp 里面的值
        # dp[i][j] 表示从第 0 行第 0 列到达第 i 行第 j 列时不同路径的数量
        for i in range( 1 , m ):

            for j in range( 1 , n ):
                # 由于每次只能向下或者向右移动一步
                
                # 如果此时出现了障碍，那么由于无法到达这个位置，因此不用处理
                if  obstacleGrid[i][j] == 1  : continue

                # 位置 (i,j) 的不同路径的数量是由
                # 1、上边位置 dp[ i - 1 ][j] 的不同路径的数量
                # 2、左边位置 dp[i][ j - 1 ] 的不同路径的数量
                # 两者之和获取到的
                dp[i][j] = dp[ i - 1 ][j] + dp[i][ j - 1 ]


        # dp[ m - 1][ n - 1 ] 表示从第 0 行第 0 列到达第 m - 1 行第 n - 1 列时不同路径的数量
        # 即到达终点的数量
        # 返回这个结果即可
        return dp[ m - 1 ][ n - 1 ]